//
//  ThreadBT.hpp
//  ThreadBT
//
//  Created by chenyh on 2021/2/8.
//

#ifndef ThreadBT_hpp
#define ThreadBT_hpp

#include <iostream>
/**
 2.3 线索二叉树
 前面我们学习了二叉树的相关知识，我们知道二叉树按照某种方式遍历的话可以产生 排序的结点序列，在这个序列中我们可以知道，除了第一个元素没有直接前驱结点，最后 一个元素没有直接后继结点，其他元素在这种序列中有且只有一个直接前驱结点和一个直 接后继结点。但是，结点的直接前驱和直接后继结点到底是哪一个结点呢?我们无法从二 叉树的结构中直接知道，只有按照这种遍历方式对二叉树进行遍历的过程中才能知道。那 么，可不可以有一种结构能够让我们直接获取到二叉树结点的前驱和后继呢?答案是肯定 的，本节介绍的线索二叉树就是这么一种特别的二叉树结构。
 2.3.1 线索二叉树的定义
 线索二叉树是一种每个结点都保留了它的直接前驱和直接后继结点信息的二叉树结 构。我们利用二叉树链式存储结构中的空的指针来存储结点的直接前驱结点指针和直接后 继结点指针，这些指针被称为线索，所以利用线索来保留前驱结点和后继结点信息的二叉 树被称为线索二叉树。
 从上面的定义知道，线索二叉树的前驱和后继的指向与使用什么样的遍历方式有关， 所以一般线索二叉树会分为前序线索二叉树、中序线索二叉树和后序线索二叉树 3 种。线 索二叉树之间的区别就是根据不同的遍历方式，其结点的前驱和后继不同。我们设定结点 左指针指向前驱结点，右指针指向后继结点。
 如何来判断结点中的指针是指向孩子结点的指针还是线索呢?一般来说有两种处理 方法。
 1)改变结点的结构，增加两个标志量，如图 2-14 所示。
 在结点中增加 lFlag 和 rFlag 两个整型标志量，当 lChild 或 rChild 是指向孩子结点的指 针时，其相应的标志量为 1，为线索时，其相应的标志量为 0。
 2)不改变结点对的结构，在表示线索的地址值(线索也是指针，也是地址值)前面 加上负号。这种方式节省了空间，但是在进行地址运算时需要额外的处理。
 2.3.2 线索二叉树的基本操作
 线索二叉树的基本操作主要有查找某个结点的前驱和后继结点，利用线索二叉树遍历 二叉树和线索二叉树的更新等。我们以中序线索二叉树为例来讲解基本操作。
   本节的线索二叉树采用增加两个标志量的结构，新的结点结构如下:
 */

template <typename DataType> class ThreadBT;
template <typename DataType>
class ThreadBTNode {
private:
    ThreadBTNode<DataType> *lChild,*rChild;
    int lFlag,rFlag;
    DataType data;
public:
    friend class ThreadBT<DataType>;
    ThreadBTNode(DataType newData) //带数据构造函数
    {
        lFlag=rFlag=0;
        this->data=newData;
        lChild=rChild=NULL;
    }
    ThreadBTNode()
    {
        lFlag=rFlag=0;
        lChild=rChild=NULL;
    }
};

template <typename DataType>
class ThreadBT {
private:
    ThreadBTNode<DataType> *root;
public:
    ThreadBT()
    {
        root = NULL;
    }
    ThreadBT(DataType data)
    {
        root = new ThreadBTNode<DataType>(data);
    }
    
    ThreadBTNode<DataType> * prior(ThreadBTNode<DataType> *node);
    ThreadBTNode<DataType> * succ(ThreadBTNode<DataType> *node);
    void inOrder();
    /// 将结点p插入到结点s后，使其成为它的右孩子
    /// @param s 被插入结点s
    /// @param p 待插入结点p
    void update(ThreadBTNode<DataType> *s,ThreadBTNode<DataType> *p);
};
/*
1.寻找结点 node 的前驱结点
我们对线索二叉树进行一次中序遍历就能明白，结点 node 的前驱必然是其左子树中最
右边的结点，所以我们可以得到算法如下:
 */
template <typename DataType>
ThreadBTNode<DataType> * ThreadBT<DataType>:: prior(ThreadBTNode<DataType> *node) {
    ThreadBTNode<DataType> *s; //设置访问结点指针
    s = node->lChild;
    if (node->lFlag == 1) { //判断s是否线索，如果线索则直接返回
        while (s->rFlag == 1) { //循环寻找结点的右子结点，找到node左子树中的最右结点
            s = s->rChild;
        }
    }
    return s;   //返回node的前驱
}
/*
 2.寻找结点 node 的后继结点
 寻找结点的后继与寻找前驱结点的方式类似，node 的后继结点是右子树中最左的结
 点，代码如下:
 */
template <typename DataType>
ThreadBTNode<DataType> * ThreadBT<DataType>:: succ(ThreadBTNode<DataType> *node) {
    ThreadBTNode<DataType> *s; //设置访问结点指针
    s = node->rChild;
    if (node->rFlag == 1) { //判断s是否线索，如果线索则直接返回
        while (s->lFlag == 1) { //循环寻找结点的右子结点，找到node左子树中的最右结点
            s = s->lChild;
        }
    }
    return s;   //返回node的前驱
}

/* 3.利用线索二叉树遍历二叉树
 线索二叉树的中序遍历的起始结点就是该二叉树最左边的结点，所以我们只需要找到 起始结点然后就可以根据线索二叉树的特点通过线索来遍历二叉树。这里，我们可以利用 前面设计的寻找结点的前驱结点和后继结点的算法。
 */
template <typename DataType>
void ThreadBT<DataType>:: inOrder() {
    if (root != NULL) {
        ThreadBTNode<DataType> *s;
        s=root;
        while (prior(s) != NULL) { //找到起始结点
            s = prior(s);
        }
        while (succ(s) != NULL) { //从起始结点开始遍历后继结点
            std::cout<<s->data<<std::endl;
            s = succ(s);
        }
    }
}
/*  4.线索二叉树的更新
 线索二叉树的更新比较麻烦，因为插入和删除结点之后，线索二叉树的相关结点的前 驱和后继将会变化，这里我们只介绍一种比较简单的情况，将结点 p 插入到结点 s 后，使 其成为它的右孩子。
 */
template <typename DataType>
void ThreadBT<DataType>:: update(ThreadBTNode<DataType> *s, ThreadBTNode<DataType> *p) {

    ThreadBTNode<DataType> *next;
    next = root;
    p->rChild = s->rChild;
    p->rFlag = s->rFlag;
    //如果s右子树为空，则s的直接后继就称为p的直接后继
    //如果s右子树不为空，则s右子树就称为p的右子树
    p->lChild = s;  //s成为p的直接前驱
    p->lFlag = 0;   //设置线索标志
    s->rChild = p;  //p将成为s的右孩子
    s->rFlag = 1;   //更改标志
    if (p->rFlag == 1) {
        next = succ(p);//找到p的后继结点
        next->lChild = p;
    }

}
/*
二叉查找树是一种具有良好排序和查找性能的二叉树数据结构。它支持多种基本操 作，包括查找、按序遍历、求最大值和最小值、查找前驱结点和后继结点、插入和删除结 点等。一般我们将它用于查找字典或优先队列结构。这些操作在二叉查找树上的平均执行 时间是O(log2 n)。
*/

#endif /* ThreadBT_hpp */
